#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tt = 0; tt < t; ++tt) {
        int n;
        cin >> n;

        int minPre = 0;
        int maxPre = 0;
        int minW = INT_MAX;// 无环最小值
        int maxW = 0;// 无环最大值
        int sum = 0;
        int tmp;
        for (int i = 0; i < n; ++i) {
            cin >> tmp;
            sum += tmp;
            if (minPre <= 0) {
                minPre += tmp;
            } else {
                minPre = tmp;
            }
            minW = min(minW, minPre);
            if (minW > minPre) {
                minW = minPre;
            }

            if (maxPre > 0) {
                maxPre += tmp;
            } else {
                maxPre = tmp;
            }
            maxW = max(maxW, maxPre);
        }
        // 有环最大值 = max(无环最大值, 数组总和-无环最小值)
        cout << max(maxW, sum - minW) << endl;
    }

    return 0;
}